package leetcode.editor.cn;
//Java：最长回文子串
public class LongestPalindromicSubstring{
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        String badabdc = solution.longestPalindrome("cdc");
        System.out.println(badabdc);
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            //1、处理临界情况就是s为空字符串，直接返回
            if (s == null || s.length() < 1) {
                return "";
            }
            //2、声明两个必要的变量值，分别用于记录最大回文子串的开始和结束位置
            int start = 0, end = 0;

            //3、循环遍历寻找最大回文子串
            for (int i = 0; i < s.length(); i++) {
                //3.1 同时处理从该位置开始的回文子串长度计算，同时处理回文子串是基数或者偶数的情况
                int len1 = expandAroundCenter(s, i, i); // 考虑回文子串是奇数的情况
                int len2 = expandAroundCenter(s, i, i + 1); // 考虑回文子串是偶数的情况
                //3.2 找出两种情况的最大值
                int len = Math.max(len1, len2);
                //3.3 判断此次的最大值是否大于上次记录的起始和结束位置的差值，大于的话，更新最大回文子串的开始和结束位置
                if (len > end - start) {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            //4、通过记录的开始和结束位置，返回最大回文子串
            return s.substring(start, end + 1);
        }

        // 从左右两个中心点向两侧扩展，返回回文长度
        private int expandAroundCenter(String s, int left, int right) {
            //从此left和right位置开始，往两边扩展，找到第一个值不相等的位置，计算出这个的长度
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            return right - left - 1; // 返回右侧和左侧索引之间的差值，也就是整个对称字符串的长度
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}